package jianzhioffer.array;

/**
 * Created by yzy on 2020-04-26 19:46
 */
public class MinNumberInRotateArray {

    public static void main(String[] args) {
        int[] arr = new int[]{666,667,2,2,2,3,4};
        System.out.println(minNumberInRotateArray(arr));
        System.out.println(minNumberInRotateArray_binary(arr));
    }

    /**
     * 由于数字是向右非单调递减的，所以rotate以后，相当于两个有序数组的拼接
     * 可以用二分法，找到处在谷底的那个元素即可
     * @param array
     * @return
     */
    public static int minNumberInRotateArray_binary(int [] array) {
        if(array.length==0) return 0;
        int low = 0;
        int high = array.length - 1;
        int mid = 0;
        while(low < high){
            // 子数组是非递减的数组
            if (array[low] < array[high]){
                return array[low];
            }

            mid = low + (high - low) / 2;
            if(array[mid] > array[low]){
                low = mid + 1;
            } else if(array[mid] < array[high]){
                high = mid;
            } else {
                low++;
            }
        }
        return array[low];
    }

    private static int binarySearch(int[] arr, int left, int right){
        if(arr[left] <= arr[right]){
            return arr[left];
        }
        if(right-left == 1){
            return Math.min(arr[left], arr[right]);
        }
        int mid = (right+left) / 2;
        if(arr[mid] < arr[left]){
            return binarySearch(arr, left, mid);
        }else{
            return binarySearch(arr, mid, right);
        }
    }

    /**
     * 思路：
     * 从前往后找
     * 数组是非递减顺序的，rotate。
     * 这样的，其实是有序的，只不过是两个非递减的数组而已。
     * 找到两个数组的交点，第二个数组的第一个元素就是。
     *
     * 注意：
     * 第一个和最后一个是最小元素的情况。
     * 遍历完了还没找到最小，那就看flag，如果flag=true那就是最后一个，否则是第一个
     * @param array
     * @return
     */
    public static int minNumberInRotateArray(int [] array) {
        boolean flag = false;
        int pre = 0;
        for(int i=0; i<array.length; i++){
            int curr = array[i];
            if(pre > curr){
                flag = true;
            }else if(flag){
                return pre;
            }
            pre = curr;
        }
        if(flag){
            return array[array.length-1];
        }else{
            return array[0];
        }
    }
}
